package main;

import datatype.Vertex;

/**
 * @author Artur Tolstenco
 *
 */

/**
 * Priority Queue implemented as heap
 */
public class PriorityQueue {
	private PriorityQueueElem[] elems;
	private int indexes[];
	private int lastIndex;
	

	/**
	 * Create an empty Priority Queue with the size = size
	 * @param size the size of the Priority Queue
	 * @throws IllegalArgumentException
	 */
	public PriorityQueue(int size) throws IllegalArgumentException {
		if (size <= 0)
			throw new IllegalArgumentException("Size must be positive number (greater than zero)!");
		
		elems = new PriorityQueueElem[size+1];
		indexes = new int[size];
		for (int i = 0; i < size; i++)
			indexes[i] = -1;
		
		lastIndex = 0;
		
	}
	
	/**
	 * @return if the queue is empty
	 */
	public boolean isEmpty() {
		return lastIndex == 0;
	}
	
	/**
	 * Add a vertex with the distance to the Priority Queue
	 * @param vertex to add to the Priority Queue
	 * @param distance the priority of the vertex to be added
	 * @throws IllegalArgumentException
	 */
	public void add(Vertex vertex, Double distance) throws IllegalArgumentException {
		if (lastIndex == elems.length-1)
			throw new IllegalArgumentException("The size of the queue is fixed! Cannot add the element!");
		
		elems[++lastIndex] = new PriorityQueueElem(vertex, distance);
		moveUp(lastIndex);
	}
	
	/**
	 * Returns and delete from the queue the vertex with the minimum distance a.k.a. with
	 * the maximum priority
	 * @return the vertex with the highest priority / with the minimum distance
	 * @throws IllegalArgumentException
	 */
	public Vertex deleteMin() throws IllegalArgumentException {
		if (lastIndex == 0) 
			throw new IllegalArgumentException("The queue is empty! No minimum element!");
		
		PriorityQueueElem minimum = elems[1];
		indexes[getIndexVertex(minimum.vertex)] = -1;
		
		if (lastIndex == 1) 
			lastIndex = 0;
		else {
			elems[1] = elems[lastIndex--];
			moveDown(1);
		}
	
		return minimum.getVertex();
	}
	
	/**
	 * Given the vertex changes its minimumDistance and updates the Priority Queue
	 * @param vertex to change the minimuimDistance
	 * @param newDistance the new distance to assign to the vertex
	 * @throws IllegalArgumentException
	 */
	public void changePriority(Vertex vertex, Double newDistance) throws IllegalArgumentException {
		int i = indexes[getIndexVertex(vertex)];
		
		if (i == -1) return;

		if (i > lastIndex) 
			throw new IllegalArgumentException("The element with index = " + i + "does not exists");
		
		//cannot put here delta = elems[i].getMinDistance() - newDistance because Infinity - N = infinity!!!
		if (newDistance > elems[i].getMinDistance()) {
			elems[i].setMinDistance(newDistance);
			moveDown(i);
		} else if (newDistance < elems[i].getMinDistance()) {
			elems[i].setMinDistance(newDistance);
			moveUp(i);
		}
		
	}
	
	/**
	 * updates the queue putting the element of index i in order
	 * @param i
	 */
	private void moveUp(int i) {
		if (i>lastIndex) return;
		
		PriorityQueueElem elem = elems[i];
		
		while (i > 1 && elem.getMinDistance() < elems[i/2].getMinDistance()) {
			updateElemAt(i, elems[i/2]);
			i /= 2;
		}
		
		updateElemAt(i, elem);
		
	}
	
	/**
	 * updates the queue putting the element of index i in order
	 * @param i
	 */
	private void moveDown(int i) {
		if (i>lastIndex) return;
		
		PriorityQueueElem elem = elems[i];
		
		for (int j = 2*i; j <= lastIndex; j = 2*i) {
			if (j+1 <= lastIndex && elems[j+1].getMinDistance() < elems[j].getMinDistance()) j++;
			if (elem.getMinDistance() <= elems[j].getMinDistance()) break;
			updateElemAt(i, elems[j]);
			i = j;
		}
		
		updateElemAt(i, elem);
		
	}
	
	private void updateElemAt(int i, PriorityQueueElem elem) {
		elems[i] = elem;
		indexes[getIndexVertex(elems[i].vertex)] = i;
	}
	
	private int getIndexVertex(Vertex vertex) {
		int index = vertex.getIndex();
		if (index < 0 || index > indexes.length)
			throw new IllegalArgumentException("The index of the vertex is not valid to be used in this queue");
		return index;
	}
	
	private class PriorityQueueElem {
		private Vertex vertex;
		private double minDistance;
		
		private PriorityQueueElem(Vertex vertex, double minDistance) {
			this.vertex = vertex;
			this.minDistance = minDistance;
		}
		/**
		 * @return the minDistance
		 */
		private double getMinDistance() {
			return minDistance;
		}
		/**
		 * @param minDistance the minDistance to set
		 */
		private void setMinDistance(double minDistance) {
			this.minDistance = minDistance;
		}
		/**
		 * @return the vertex
		 */
		private Vertex getVertex() {
			return vertex;
		}
		
		
	}


}
